package main

// 插入排序的定义就是
// 将元素向有序集合中进行插入
func InsertSort(nums []int) {
	// 假设 第一个元素（只有一个元素）为有序状态，将后序元素往前插入
	for i := 1; i < len(nums); i++ {
		temp, j := nums[i], i
		for ; j > 0 && nums[j-1] > temp; j-- {
			// 1. 交换，找到正确的位置插入
			// nums[j], nums[j - 1] = nums[j - 1], nums[j]
			// 2. 这里使用直接覆盖的方式
			nums[j] = nums[j-1]
		}
		nums[j] = temp
	}
}

//func main() {
//	arr := []int{54, 26, 93, 17, 77, 31, 44, 55, 20}
//	InsertSort(arr)
//	fmt.Println(arr)
//}
